package 中等.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个大小为 m x n 的二进制矩阵 grid ，
 * 其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
 * 一次 移动 是指从一个陆地单元格走到另一个相邻
 * （上、下、左、右）的陆地单元格或跨过 grid 的边界。
 * 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-enclaves
 */
public class 飞地的数量_1020 {

    public static void main(String[] args) {

        //[[0,0,0,1,1,1,0,1,1,1,1,1,0,0,0],
        // [1,1,1,1,0,0,0,1,1,0,0,0,1,1,1],
        // [1,1,1,0,0,1,0,1,1,1,0,0,0,1,1],
        // [1,1,0,1,0,1,1,0,0,0,1,1,0,1,0],
        // [1,1,1,1,0,0,0,1,1,1,0,0,0,1,1],
        // [1,0,1,1,0,0,1,1,1,1,1,1,0,0,0],
        // [0,1,0,0,1,1,1,1,0,0,1,1,1,0,0],
        // [0,0,1,0,0,0,0,1,1,0,0,1,0,0,0],
        // [1,0,1,0,0,1,0,0,0,0,0,0,1,0,1],
        // [1,1,1,0,1,0,1,0,1,1,1,0,0,1,0]]
        int[][] gird = {{0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0}, {1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1}, {1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0}, {1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1}, {1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0}};
        System.out.println(numEnclaves(gird));

    }

    /**
     * 将边界的陆地放进队列，广度搜索相邻的陆地，至为0
     * 遍历格子所有为1的陆地即为无法跳出格子的
     * 注意：确保放入队列的陆地，已经是被标记过0
     *
     * @param grid
     * @return
     */
    public static int numEnclaves(int[][] grid) {
        int ans = 0;
        //定义四个方向
        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> queue = new ArrayDeque<>();
        int rows = grid.length;
        int columns = grid[0].length;
        for (int column = 0; column < columns; column++) {
            if (grid[0][column] == 1) {  //第一行
                queue.offer(new int[]{0, column});
                grid[0][column] = 0;
            }
            if (grid[rows - 1][column] == 1) {   //最后一行
                queue.offer(new int[]{rows - 1, column});
                grid[rows - 1][column] = 0;
            }
        }
        for (int row = 1; row < rows - 1; row++) {
            if (grid[row][0] == 1) {  //第一列
                queue.offer(new int[]{row, 0});
                grid[row][0] = 0;
            }
            if (grid[row][columns - 1] == 1) {  //最后一列
                queue.offer(new int[]{row, columns - 1});
                grid[row][columns - 1] = 0;
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                int curRow = cur[0];
                int curColumn = cur[1];
                for (int[] direct : direction) {
                    int nextRow = direct[0] + curRow;
                    int nextColumn = direct[1] + curColumn;
                    if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns
                            && grid[nextRow][nextColumn] == 1) {  //注意：同一层的元素可以会存在重复元素
                        grid[nextRow][nextColumn] = 0;  //这里每次放进队列的陆地直接进行标记
                        queue.offer(new int[]{nextRow, nextColumn});
                    }
                }
            }
        }
        for (int row = 1; row < rows - 1; row++) {  //无需遍历边界的陆地
            for (int column = 1; column < columns - 1; column++) {
                if (grid[row][column] == 1) {
                    ans++;
                }
            }
        }
        return ans;
    }


    /**
     * 遍历一遍，碰到陆地将周围相邻的的陆地全部搜索出来，
     * 如果当中存在边界，那么不累计数量
     * 不存在边界，将陆地数量累加
     *
     * @param grid
     * @return
     */
    public static int numEnclaves2(int[][] grid) {
        int ans = 0;
        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> queue = new ArrayDeque<>();
        int rows = grid.length;
        int columns = grid[0].length;
        for (int row = 1; row < rows - 1; row++) {  //排除边界遍历
            for (int column = 1; column < columns - 1; column++) {
                int curAns = 0;
                boolean flag = true;
                if (grid[row][column] == 1) {
                    grid[row][column] = 0;
                    queue.offer(new int[]{row, column});
                    while (!queue.isEmpty()) {
                        int size = queue.size();
                        curAns += size;
                        while (size-- > 0) {
                            int[] cur = queue.pollFirst();
                            int curRow = cur[0];
                            int curColumn = cur[1];
                            for (int[] direct : direction) {
                                int nextRow = direct[0] + curRow;
                                int nextColumn = direct[1] + curColumn;
                                if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns
                                        && grid[nextRow][nextColumn] == 1) {
                                    if (nextRow == 0 || nextRow == rows - 1 || nextColumn == 0 || nextColumn == columns - 1) {
                                        flag = false;  //包含边界的岛屿不能累计
                                    }
                                    grid[nextRow][nextColumn] = 0;
                                    queue.offer(new int[]{nextRow, nextColumn});
                                }
                            }
                        }
                    }
                    if (flag) {
                        ans += curAns;
                    }
                }
            }
        }
        return ans;
    }


}
